#!/usr/bin/env python

import sys

class node:
	def __init__(self, number, bits = 0, time = 0):
		self.bits = bits
		self.time = time
		self.id = number
	def __cmp__(self, other):
		if self.bits > other.bits:
			return 1
		elif self.bits < other.bits:
			return -1
		return 0
	def __str__(self):
		return "("+ "ID: "+ str(self.id) +" bits: " + str(self.bits) + " time: " + str(self.time) + ")"
	def __repr__(self):
		return self.__str__()		

# Linear Schedule function recieves the capacity restriction, which will be used
# to check if the set is a valid one. The stream argument is an instance of nodes of
# (bits, time).
# This algorithm takes O(n) to verify if the set is a valid one 

def schedule_valid_l(streams, restriction):	
	assert restriction >= 0, "Restriction less than 0 (%d)" % restriction
	assert len(streams) > 0, "Empty stream"
	t = b = 0
	for elem in streams:	
		assert elem.bits >= 0 and elem.time >= 0, "Invalid element in stream"
		t += elem.time
		b += elem.bits
	return b <= t * restriction

# Linear Schedule function recieves the capacity restriction, which will be used
# to check if the set is a valid one. The stream argument is an instance of nodes of
# (bits, time).
# This algorithm, based on the hypothesis that dictionaries take O(1) for
# any operation, takes o(n) time to solve the scheduling problem in our best case scenario. In the
# worst case scenario, it will take O(n log n)

def schedule_improved(streams, restriction):
	# assert that checks that the restriction is not negative
	assert restriction >= 0, "Restriction less than 0 (%d)" % restriction
	# must have some element in the stream. Testing purposes only, later
	# it will be replaced for an if len(stream) == 0: return []
	assert len(streams) > 0, "Empty stream"
	waiting = streams[:]
	#heap that will contain the rejected in the first try, will be used as a buffer
	visited = []
	solution_set = []
	t = 0
	b = 0
	n = len(streams)
	# for every element in our set we will make an attempt to put it in our set
	# this is the linear part of the algoritm. This will grant us the o(n) part of the
	# deal for the best case scenario
	for elem in waiting:
		t += elem.time
		b += elem.bits
		if b <= restriction * t:
			solution_set.append(elem)
			n -= 1
		else:
			t -= elem.time
			b -= elem.bits
			visited.heappush(elem)
	# if some elements have been rejected, we will be dealing with a O(n log n) case
	# scenario
	while (n >= 0):
		elem = visited.heappop()
		t += elem.time
		b += elem.bits
		# the case that we have an invalid set
		if b >= restriction * t:
			return []
		# the happy path, the element can be inserted
		else:
			solution_set.append(elem)
			n -= 1
		 
	# if it comes the case that we are here, we have found the solution
	return solution_set
		
		
# Schedule function recieves the capacity restriction, which will be used
# to check if the set is a valid one. The stream argument is a list of 
# tuples (bits, time).
# This algorithm takes O(n log n) in a worst case scenario, where n stands
# for the number of streams in our set.

def schedule(streams, restriction):
	# assert that checks that the restriction is not negative
	assert restriction >= 0, "Restriction less than 0 (%d)" % restriction
	# must have some element in the stream. Testing purposes only, later
	# it will be replaced for an if len(stream) == 0: return []
	assert len(streams) > 0, "Empty stream"
	t = 0
	b = 0
	# sorted uses Timsort, whose worst case is O(n log n)
	aux_set = sorted(streams,key=lambda st: st.bits)
	solution_set = []
	for elem in aux_set:
		# checks that our set does not break our hypothesis
		assert elem.bits >= 0 and elem.time >= 0, "Invalid element in stream"
		t += elem.time
		b += elem.bits
		if b > t * restriction:
			return []
		solution_set.append(elem)
	return solution_set

def manage_l(streams, r):
	print "Validation through linear algorithm. No visible solution available"
	if (schedule_valid_l(streams,r)):
		print "The set is a valid one."
	else:
		print "The set has no valid configuration."

def manage_n(streams, r):
	print "Validation through n log n algorithm. Final solution available"
        sol = schedule(streams, r)
	if (len(sol) != 0):
                print "The set is a valid one."
		print "Solution:"
		print sol
        else:
                print "The set has no valid configuration."


def format_input(inp):
	fdesc = open(inp, "r")
	lines = fdesc.readlines()
	elements = map(lambda s: s.replace("\n",""), filter(lambda s: s != "\n", lines))
	r = int(filter(lambda s: s != "r:", elements[0].split())[0])
	streams = []
	elements.pop(0)
	for line in elements:
		sline = line.split()
		num = int(sline[0].replace(":",""))
		b = int(sline[1].replace("(","").replace(",",""))
		t = int(sline[2].replace(")", ""))
		node(num, b, t)
		streams.append(node(num, b, t))
	return r, streams

def main():
	if len(sys.argv) != 3:
		print "Uso correcto: schedule.py [-l o -n] archivo"
		sys.exit(1)
	args = {"-l": False, "-n": False}
	sys.argv.pop(0)
	inp = ""
	for elem in sys.argv:
		if elem in args:
			args[elem] = True
		else:
			inp = elem
	streams = []
	r = 0
	try:
		r, streams = format_input(inp)
	except:
		print "Invalid or incorrect file"
	if args["-l"]:
		manage_l(streams, r)
	if args["-n"]:
		manage_n(streams, r)

main()
